//import java.util.HashMap;
//import java.util.Arrays;
//import java.util.Map;
class Solution {
    public String longestPalindrome(String s) {
        int n=s.length();
        boolean[][] dp=new boolean[n][n];
        int len=1,begin=0;
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s.charAt(i)==s.charAt(j))
                    dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                if(dp[i][j]&&len<j-i+1){
                    begin=i;
                    len=j-i+1;
                }
            }
        }
        return s.substring(begin,begin+len);
    }
}